import java.util.HashMap;
import java.util.Map;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/12 10:01
 * @description:
 */
public class Solution149 {
    public int maxPoints(int[][] points) {
        if (points.length <= 2) {
            return points.length;
        }
        int maxCount = 0;
        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> kMap = new HashMap<>();
            // 与当前基准点重合的点数量（至少包含基准点自身）
            int samePoint = 1;
            // 当前基准点下的最大共线点数（不包含重复点）
            int currentMax = 0;
            int x1 = points[i][0];
            int y1 = points[i][1];
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int x2 = points[j][0];
                int y2 = points[j][1];
                if (x1 == x2 && y1 == y2) {
                    samePoint++;
                    continue;
                }
                int deltaY = y2 - y1;
                int deltaX = x2 - x1;
                int gcd = gcd(Math.abs(deltaX), Math.abs(deltaY));
                int reduceDx = deltaX / gcd;
                int reduceDy = deltaY / gcd;
                if (reduceDx < 0) {
                    reduceDx = -reduceDx;
                    reduceDy = -reduceDy;
                }
                String k = reduceDy + "," + reduceDx;
                kMap.put(k, kMap.getOrDefault(k, 0) + 1);
                currentMax = Math.max(currentMax, kMap.get(k));
            }
            // 当前基准点下的最大共线点数 = 同斜率点的最大数量 + 重复点数量
            maxCount = Math.max(maxCount, currentMax + samePoint);
        }
        return maxCount;
    }

    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    public static void main(String[] args) {
        Solution149 solution = new Solution149();
        System.out.println(solution.maxPoints(new int[][]{{1, 1}, {2, 2}, {3, 3}}));
        System.out.println(solution.maxPoints(new int[][]{{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}}));
    }
}
